﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;


//淘宝网店
//https://www.nowcoder.com/questionTerminal/754921e9c98b43d1b2d70c227b844101
////通过年月获取当月天数
//int GetDay(int year, int month)
//{
//    int day[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//    //闰年-2月有29天
//    if (2 == month && ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))) { return day[month] + 1; }
//    return day[month];
//}
//
//struct ti
//{
//    int year = 0;
//    int month = 0;
//    int day = 0;
//
//    bool operator==(const ti& t) { return year == t.year && month == t.month; }
//    bool operator!=(const ti& t) { return !(*this == t); }
//    bool operator<(const ti& t) { return (year < t.year || year == t.year && month < t.month); }
//    int operator++()
//    {
//        if (month + 1 > 12)
//        {
//            ++year;
//            month = 1;
//        }
//        else ++month;
//
//        return month;
//    }
//};
//
////2 3 5 7 11为素数
//long long money(ti t1, ti t2)
//{
//    long long ret = 0;
//    int diff = 0;
//    if (t1 == t2) diff = t2.day - t1.day + 1; //如果仅仅在当月
//    else diff = GetDay(t1.year, t1.month) - t1.day + 1; //不同年份
//
//    int m = t1.month;
//    if (m == 2 || m == 3 || m == 5 || m == 7 || m == 11) ret += diff;
//    else ret += diff * 2;
//    ++t1;
//    while (t1 < t2)
//    {
//        m = t1.month;
//        diff = GetDay(t1.year, t1.month);
//        if (m == 2 || m == 3 || m == 5 || m == 7 || m == 11) ret += diff;
//        else ret += diff * 2;
//        ++t1;
//
//        if (t1 == t2)
//        {
//            m = t1.month;
//            diff = t2.day;
//            if (m == 2 || m == 3 || m == 5 || m == 7 || m == 11) ret += diff;
//            else ret += diff * 2;
//
//            break;
//        }
//    }
//    return ret;
//}
//
//int main() {
//    ti t1, t2;
//    while (cin >> t1.year >> t1.month >> t1.day >> t2.year >> t2.month >> t2.day) { // 注意 while 处理多个 case
//        cout << money(t1, t2) << endl;
//    }
//    return 0;
//}



//斐波那契凤尾
//https://www.nowcoder.com/questionTerminal/c0a4b917a15f40a49ca10532ab9019fb
//int main() {
//    int n;
//
//    //因为牛客的一整套测试用例 考虑到性能问题 提前计算所有斐波那契 然后根据下标使用
//    int fib[100001] = { 0 }; //多开一个空间下标对齐
//    fib[0] = fib[1] = 1;
//    for (int i = 2; i < 100001; ++i) //填充斐波那契表
//        fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000;
//    //只取斐波那契后六位进行计算 不影响结果
//
//    while (cin >> n) { // 注意 while 处理多个 case
//        if (n < 25) printf("%d\n", fib[n]);
//        else printf("%06d\n", fib[n]); //控制格式输出
//    }
//    return 0;
//}

//暴力计算函数
//int fibnum(int n)
//{
//    int left = 1;
//    int right = 1;
//    if (n < 2) return left;
//    for (int i = 2; i <= n; ++i)
//    {
//        int tmp = (left + right)%1000000;
//        left = right;
//        right = tmp;
//    }
//    return right;
//}